|
In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since the other direction is trivial, we can say that P = NP if and only if NPI is empty. Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property: Schaefer's dichotomy theorem provides conditions under which classes of constrained Boolean satisfiability problems can not be in NPI. Some problems that are considered good candidates for being NP-intermediate are the graph isomorphism problem, factoring, and computing the discrete logarithm. == List of problems that might be NP-intermediate〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237〕 == * Factoring integers * Isomorphism problems: Graph isomorphism problem, Group isomorphism problem, Group automorphism, Ring isomorphism, Ring automorphism * Computing the rotation distance〔(Rotation distance, triangulations, and hyperbolic geometry ) 〕 between two binary trees or the flip distance between two triangulations of the same convex polygon * The turnpike problem〔(Reconstructing sets from interpoint distances ) 〕 of reconstructing points on line from their distance multiset * Discrete Log Problem and others related to cryptographic assumptions * Determining winner in parity games〔http://kintali.wordpress.com/2010/06/06/np-intersect-conp/〕 * Determining who has the highest chance of winning a stochastic game〔 * Numbers in boxes problems〔http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html〕 * Agenda control for balanced single-elimination tournaments〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460〕 * Knot triviality〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1106#1106〕 * Assuming NEXP is not equal to EXP, padded versions of NEXP-complete problems * Problems in TFNP〔(On total functions, existence theorems and computational complexity )〕 * Intersecting Monotone SAT〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739〕 * Minimum Circuit Size Problem〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745〕 * Deciding whether a given triangulated 3-manifold is a 3-sphere * The cutting stock problem with a constant number of object lengths〔http://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827〕 * Monotone self-duality〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950〕 * Planar minimum bisection〔(Approximability of the Minimum Bisection Problem: An Algorithmic Challenge ) 〕 * Pigeonhole subset sum〔http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality〕 * Determining the result of a comparison between two sums of square roots of integers〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010〕 * Deciding whether a graph admits a graceful labeling〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384〕 * Gap version of the closest vector in lattice problem〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806〕 * The linear divisibility problem〔http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331〕 * Finding the VC dimension * Clustered planarity〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「NP-intermediate」の詳細全文を読む スポンサード リンク
|